package com.andnnl.shudu;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

/**
 * Created by chenss on 2017/11/14.
 */
public class ShuDuCal {
    int count = 0;

    public static void main(String[] args) {
        test2();
    }


    private static void test2() {
//        for(int i=0;i<9;i++)
//            for(int j=0;j<9;j++)
//                a[i][j]=;
        new ShuDuCal().start();
    }

//    static String source = ""
//            + "7 0 0 1 4 8 0 0 0"
//            + "3 0 0 0 0 6 0 0 0"
//            + "6 0 9 0 0 2 0 0 0"
//            + "0 0 0 0 1 0 2 0 0"
//            + "5 7 0 0 0 0 9 0 0"
//            + "0 0 0 7 0 0 0 6 0"
//            + "0 0 8 2 0 0 0 0 1"
//            + "0 0 4 0 0 0 0 0 0"
//            + "0 6 0 0 0 0 0 4 8";




    //5个解
//    static String source = ""
//            + "9 0 0 0 0 5 0 4 0 "
//            + "0 0 0 0 0 1 5 0 0 "
//            + "3 0 0 0 0 0 0 0 9 "
//            + "4 0 0 0 0 0 0 0 0 "
//            + "0 1 7 0 0 0 0 0 0 "
//            + "0 0 3 4 0 0 0 0 2 "
//            + "0 5 2 0 3 0 0 8 6 "
//            + "0 0 0 0 0 7 3 0 0 "
//            + "0 0 0 1 8 6 9 0 0 ";

//    static String source = ""
//            + "0 6 0 4 0 0 0 5 0 "
//            + "9 0 1 0 0 0 0 4 0 "
//            + "0 0 0 1 0 0 7 0 9 "
//            + "0 0 0 6 0 0 0 2 0 "
//            + "0 0 8 0 0 3 0 0 6 "
//            + "0 7 0 0 4 0 0 0 0 "
//            + "2 0 3 0 8 0 0 0 0 "
//            + "0 5 0 0 7 0 0 1 0 "
//            + "0 8 0 0 0 0 9 0 5 ";

    //test base 3解
//    static String source = ""
//            + "0 0 2 9 0 0 0 0 0 "
//            + "0 9 0 0 0 0 8 0 5 "
//            + "0 5 8 0 0 0 7 0 0 "
//            + "1 0 9 0 3 0 0 0 0 "
//            + "0 0 0 0 7 8 0 0 0 "
//            + "0 0 0 0 0 0 0 3 0 "
//            + "9 4 0 0 5 0 0 0 1 "
//            + "0 0 0 0 0 7 0 0 9 "
//            + "6 8 0 0 9 3 5 0 0 ";

    //88888
//    static String source = ""
//            + "0 6 0 4 0 0 0 5 0 "
//            + "9 0 1 0 0 0 0 4 0 "
//            + "0 0 0 1 0 0 7 0 9 "
//            + "0 0 0 6 0 0 0 2 0 "
//            + "0 0 8 0 0 3 0 0 6 "
//            + "0 7 0 0 4 0 0 0 0 "
//            + "2 0 3 0 8 0 0 0 0 "
//            + "0 5 0 0 7 0 0 1 0 "
//            + "0 8 0 0 0 0 9 0 5 ";
    //专家级1
    // 找到唯一矩阵,E9不能包含候选数 3,7
    // 在双数链 (D6, D7, F8) 中,   在 F8, D6 中必有一个是 8
//    static String source = ""
//            + "0 0 0 0 0 5 0 2 0 "
//            + "3 0 9 2 0 0 0 0 0 "
//            + "0 0 6 0 0 0 4 0 0 "
//            + "0 0 0 0 0 0 0 0 9 "
//            + "5 0 0 0 1 0 0 0 0 "
//            + "0 3 0 0 4 0 6 0 5 "
//            + "0 8 0 5 0 0 0 0 0 "
//            + "9 0 0 8 6 7 3 0 0 "
//            + "0 0 7 1 0 0 0 0 0 ";

//    static String source = ""
//            + "0 0 0 0 0 0 0 0 0 "
//            + "1 3 4 0 0 0 0 0 0 "
//            + "2 0 5 0 0 9 0 0 7 "
//            + "6 0 1 0 4 0 9 0 0 "
//            + "0 7 0 0 2 0 0 3 0 "
//            + "0 0 3 0 8 0 6 0 5 "
//            + "9 0 0 7 0 0 1 0 4 "
//            + "0 0 0 0 0 0 8 6 2 "
//            + "0 0 0 0 0 0 0 0 0 ";

//    static String source = ""
//            + "3,0,0,4,0,0,0,0,7"
//            + "0,0,0,0,0,0,1,0,0"
//            + "0,0,0,1,6,0,4,8,0"
//            + "2,0,4,0,0,3,0,0,0"
//            + "0,0,9,0,8,0,5,0,0"
//            + "0,0,0,6,0,0,8,0,9"
//            + "0,5,7,0,1,9,0,0,0"
//            + "0,0,8,0,0,0,0,0,0"
//            + "9,0,0,0,0,7,0,0,8";
    static String source = ""
            + "0 0 8  0 7 4  0 0 5"
            + "0 0 4  0 8 0  1 6 0"
            + "0 0 0  5 0 0  0 0 0"
            + "0 8 0  0 0 0  0 4 0"
            + "0 0 0  0 0 0  5 0 7"
            + "9 2 0  0 0 5  0 0 0"
            + "0 4 0  0 0 0  9 0 0"
            + "0 0 0  7 0 8  0 0 1"
            + "1 0 6  2 0 0  8 0 0";

// test area
//    static String source = ""
//            + "0 0 0 8 1 0 0 0 0 "
//            + "2 0 0 3 7 0 0 0 0 "
//            + "8 1 0 0 0 0 0 4 0 "
//            + "0 0 1 0 0 0 0 7 2 "
//            + "0 0 0 0 0 0 0 6 3 "
//            + "0 7 3 0 6 0 0 0 0 "
//            + "0 0 9 2 0 0 6 0 0 "
//            + "4 0 0 0 0 6 0 0 9 "
//            + "0 0 0 0 0 1 7 0 0 ";

    /**
     * 初始化数据
     *
     * @param source 空格分开的81个数字 0 表示待填
     * @return
     */
    private static int[][] init(String source) {
        source = source.replaceAll("[ ,]", "");
        int[][] data = new int[9][9];
        for (int i = 0; i < source.length(); i++) {
            //应该用source.charAt(i) - '0'
            int v = Integer.parseInt(source.charAt(i) + "");
            if (v != 0) {
//                data[i / 9][i % 9] = 1 << (v - 1);//存储2的倍数
                data[i / 9][i % 9] = v;//存储原始数
            }
        }
        return data;
    }

    private void start() {
        int[][] a = init(source);
        int[][] may = new int[81][9];//候选列表，每个格子可能填的数字，先初始化为全部有
        for (int i = 0; i < may.length; i++) {
            for (int j = 0; j < may[i].length; j++) {
                may[i][j] = 1;//存储原始数1
            }
        }
        long t1 = System.currentTimeMillis();
        filterMay(a, may);
        print(a, may);
        while (true) {
            filterMay(a, may);
            //填写候选列表中，只有1个值的情况
            if (writeMayOnlyOne(a, may)) {
                print(a, may);
                continue;
            }

            //基础摒除法
            if (baseFilter(a, may)) {
                print(a, may);
                continue;
            }

            //按区块过滤候选值
            if (areaRowMayFilter(a, may)) {
                print(a, may);
                continue;
            }
            //按区块过滤候选值
            if (areaColMayFilter(a, may)) {
                print(a, may);
                continue;
            }
            //按3链数删除法
            if (linkFilter(a, may)) {
                print(a, may);
                continue;
            }

            //唯一矩阵，2个相同值在一个矩形中，出现3次
//            最新添加唯一矩形法，这个方法利用了数独结果唯一性的特性：如果有四个构成矩形顶点的格子只使用两个数字，而且同在一行或同在一列的格子在同一个宫格中，那么这个局面的结果必然不是唯一的（交换它们使用的数字同样可以得到合法的数独结果），必然不是合法的数独局面。通过这个结论我们分别得到两种删减法:
            if (onlyMatrix(a, may)) {
                print(a, may);
                continue;
            }
//            //按区块屏蔽
//            if (areaFilter(a, may)) {
//                print(a, may);
//                continue;
//            }

            //去掉重复的数字后，开始填数字
            //先填写一行或一列中中唯一出现的数

            break;

//            System.out.println("11111111");
        }

        print(a, may);


//        SD(a, 0);
//        SD2(a, 0,may);
        long t2 = System.currentTimeMillis();
        System.out.println("ms:" + (t2 - t1));
    }

    private boolean onlyMatrix(int[][] a, int[][] may) {
        List<int[]> mayList = new ArrayList<>();
        List<Integer> idxList = new ArrayList<>();
        for (int i = 0; i < may.length; i++) {
            int row = i / 9;
            int col = i % 9;
            //先过滤当前行，排除出现过的数字
            int v = a[row][col];//当前行的每一格的值
            if (v == 0)
                idxList.add(i);
        }
        //2链数到N链数删除
        for (int level = 3; level < 4; level++) {
            int n = 0;
            List<Integer> rsList = new ArrayList<>();
            if (delMatrix(a, may, idxList, rsList, level, n))
                return true;
        }
        return false;
    }

    private boolean delMatrix(int[][] a, int[][] may, List<Integer> idxList, List<Integer> rsList, int level, int n) {
        if (n == idxList.size()) return false;
        boolean rs = false;
        for (int i = n; i < idxList.size(); i++) {
            rsList.add(idxList.get(i));
            if (rsList.size() == level) {
                //合并计算后，还是2个数，3个相同的候选数
                int[] c = new int[9];
                for (Integer idx : rsList) {
                    merge(c, may[idx]);
                }
                int len = calLen(c);
                if (len == 2) {
                    System.out.println(rsList);
                    boolean isModify = false;
                    String delStr = "";
                    //再判断，其中2个是否在同一格子中
                    //判断是否在相同的行、或者列
                    int idx1 = rsList.get(0);
                    int idx2 = rsList.get(1);
                    int idx3 = rsList.get(2);
                    int r1 = idx1 / 9;
                    int c1 = idx1 % 9;
                    int r2 = idx2 / 9;
                    int c2 = idx2 % 9;
                    int r3 = idx3 / 9;
                    int c3 = idx3 % 9;
                    int r4 = -1;
                    int c4 = -1;
                    int idx4 = -1;
                    if (r1 == r2 && c3 == c1) {
                        //构成,行相等，第1个列相等，右下角的值可以排除
                        System.out.println("1");
                        r4 = r3;
                        c4 = c2;


                    } else if (r1 == r2 && c3 == c2) {
                        //构成,行相等，第2个列相等，左下角的值可以排除
                        System.out.println("2");
                        r4 = r3;
                        c4 = c1;
                    } else if (r2 == r3 && c2 == c1) {
                        //构成,后二行相等，第1个列相等，右上角的值可以排除
                        System.out.println("3");
                        r4 = r1;
                        c4 = c3;
                    } else if (r2 == r3 && c3 == c1) {
                        //构成,后二行相等，第1个列相等，左上角的值可以排除
                        System.out.println("4");
                        r4 = r1;
                        c4 = c2;
                    } else {

                    }
                    idx4 = r4 * 9 + c4;
                    if (r4 != -1) {
                        merge(c, may[idx4]);
                        len = calLen(c);
                        if (len == 2) {
                            //4个值相等，构成
                            System.out.println("4个值相等，构成矩形删除法,TODO:删除矩形外的值");
                        } else {

                            boolean isClean = false;
                            int[] m = may[idx1];
                            int[] m1 = may[idx4];
                            for (int j = 0; j < 9; j++) {
                                if (m[j] == 1 && m1[j] == 1) {
                                    m1[j] = 0;
                                    isClean = true;
                                }
                            }
                            if (isClean) {
                                System.out.println("唯一矩形，删除候选值");
                                return true;
                            }
                        }
                    }
                }
            } else {
                rs = delMatrix(a, may, idxList, rsList, level, i + 1);
                if (rs)
                    return true;
            }
            rsList.remove(rsList.size() - 1);
        }
        return rs;
    }

    /**
     * 3链数删除法
     * 9宫格内，形成3链数、4链数，则其他的格子可排除掉3链数
     * 一行或者一列内，形成3链数、4链数，则其他的行或者列可排除掉3链数
     *
     * @param a
     * @param may
     * @return
     */
    private boolean linkFilter(int[][] a, int[][] may) {

        //收集格子内的3链数
        //一个9宫格过滤
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int row = i * 3;
                int col = j * 3;
                List<int[]> mayList = new ArrayList<>();
                List<Integer> idxList = new ArrayList<>();
                for (int r = row; r < row + 3; r++) {
                    for (int c = col; c < col + 3; c++) {
                        if (a[r][c] > 0) continue;//当前有值时，不判断，只取候选值列表
                        int idx = r * 9 + c;
                        idxList.add(idx);
                        mayList.add(may[idx]);
                    }
                }
                int gzNum = i * 3 + j + 1;
                String desc = "第" + gzNum + "个格子内";
                //2链数到N链数删除
                for (int level = 2; level < idxList.size(); level++) {
                    int n = 0;
                    List<Integer> rsList = new ArrayList<>();
                    if (delLink9(desc, a, may, idxList, rsList, level, n))
                        return true;
                }

            }
        }


        //行过滤
        for (int r = 0; r < 9; r++) {
            List<int[]> mayList = new ArrayList<>();
            List<Integer> idxList = new ArrayList<>();
            for (int c = 0; c < 9; c++) {
                if (a[r][c] > 0) continue;//当前有值时，不判断，只取候选值列表
                int idx = r * 9 + c;
                idxList.add(idx);
                mayList.add(may[idx]);
            }
            String desc = "第" + (r + 1) + "行";
            //2链数到N链数删除
            for (int level = 2; level < idxList.size(); level++) {
                int n = 0;
                List<Integer> rsList = new ArrayList<>();
                if (delLink9(desc, a, may, idxList, rsList, level, n))
                    return true;
            }
        }

        //列过滤
        for (int c = 0; c < 9; c++) {
            List<int[]> mayList = new ArrayList<>();
            List<Integer> idxList = new ArrayList<>();
            for (int r = 0; r < 9; r++) {
                if (a[r][c] > 0) continue;//当前有值时，不判断，只取候选值列表
                int idx = r * 9 + c;
                idxList.add(idx);
                mayList.add(may[idx]);
            }
            String desc = "第" + (c + 1) + "列";
            //2链数到N链数删除
            for (int level = 2; level < idxList.size(); level++) {
                int n = 0;
                List<Integer> rsList = new ArrayList<>();
                if (delLink9(desc, a, may, idxList, rsList, level, n))
                    return true;
            }
        }

        return false;
    }

    /**
     * @param desc
     * @param a
     * @param may
     * @param idxList 9宫格内或者一行，或者一列的候选值id
     * @param rsList
     * @param level
     * @param n
     * @return
     */
    private boolean delLink9(String desc, int[][] a, int[][] may, List<Integer> idxList, List<Integer> rsList, int level, int n) {
        if (n == idxList.size()) return false;
        boolean rs = false;
        for (int i = n; i < idxList.size(); i++) {
            rsList.add(idxList.get(i));
            if (rsList.size() == level) {
//                System.out.println(rsList);
                //合并计算后，还是3个数，则为3链数
                int[] c = new int[9];
                for (Integer idx : rsList) {
                    merge(c, may[idx]);
                }
                int len = calLen(c);
                if (len == level) {
                    boolean isModify = false;
                    String delStr = "";
                    for (Integer idx : idxList) {
                        if (rsList.contains(idx)) continue;
                        int[] ints = may[idx];
                        for (int x = 0; x < 9; x++) {
                            if (c[x] == 1 && ints[x] == 1) {//
                                ints[x] = 0;
                                isModify = true;
                                delStr += "第" + (idx / 9 + 1) + "行第" + (idx % 9 + 1) + "列,值:" + (x + 1) + ",";
                            }
                        }
                    }
                    if (isModify) {
                        String lstr = rsList.stream().map(idx2 -> getGZ(may[idx2])).collect(Collectors.joining(","));
                        System.out.println(desc + "形成" + len + "链数,链数：" + lstr + ",去掉其他候选值");
                        return true;
                    }
                }
            } else {
                rs = delLink9(desc, a, may, idxList, rsList, level, i + 1);
                if (rs)
                    return true;
            }
            rsList.remove(rsList.size() - 1);
        }
        return rs;
    }

    private boolean cleanInLink9(int[][] a, int[][] may, List<int[]> mayList, List<Integer> idxList, int gzNum) {
        if (mayList.size() <= 3) {
            return false;
        }
        for (int i = 0; i < mayList.size(); i++) {
            for (int j = i + 1; j < mayList.size(); j++) {
                for (int k = j + 1; k < mayList.size(); k++) {
                    //合并计算后，还是3个数，则为3链数
                    int[] c = new int[9];
                    merge(c, mayList.get(i));
                    merge(c, mayList.get(j));
                    merge(c, mayList.get(k));
                    int len = calLen(c);
                    if (len == 3) {
                        System.out.println("第" + gzNum + "个格子内形成3链数,去掉其他候选值：" + getGZ(mayList.get(i)) + "," + getGZ(mayList.get(j)) + "," + getGZ(mayList.get(k)));
                        mayList.remove(k);
                        mayList.remove(j);
                        mayList.remove(i);
                        boolean isModify = false;
                        for (int[] ints : mayList) {
                            for (int x = 0; x < 9; x++) {
                                if (c[x] == 1 && ints[x] == 1) {//
                                    ints[x] = 0;
                                    isModify = true;
                                }
                            }
                        }
                        if (isModify) return true;
                    }
                }
            }
        }
        //任意3个组合，存在3链数
        return false;
    }

    private int calLen(int[] c) {
        int count = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] == 1) count++;
        }
        return count;
    }

    private void merge(int[] c, int[] ints) {
        for (int i = 0; i < ints.length; i++) {
            if (ints[i] == 1) c[i] = 1;
        }
    }

    private boolean areaRowMayFilter(int[][] a, int[][] may) {
        boolean rs = false;
        //一个9宫格过滤
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int row = i * 3;
                int col = j * 3;

                for (int k = 1; k <= 9; k++) {
                    int rowCount = 0;
                    int rowIdx = 0;
                    int rowValue = 0;
                    //一行中存在多个候选值，而其他行没有
                    for (int r = row; r < row + 3; r++) {
                        boolean isFindInMay = false;
                        for (int c = col; c < col + 3; c++) {
                            if (a[r][c] > 0) continue;//当前有值时，不判断，只取候选值列表
                            if (findInMay(may, r, c, k)) {
                                isFindInMay = true;
                            }
                        }
                        if (isFindInMay) {
                            rowCount++;
                            rowIdx = r;
                            rowValue = k;
                        }
                    }
                    if (rowCount == 1) {
                        //值存在唯一行，把当前行的其他格子的候选值删除
//                        System.out.println(rowIdx);
                        if (cleanRowMay(a, may, rowIdx, col, rowValue))
                            rs = true;
                    }
                }
            }
        }
        return rs;
    }

    private boolean areaColMayFilter(int[][] a, int[][] may) {
        boolean rs = false;
        //一个9宫格过滤
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int row = i * 3;
                int col = j * 3;

                for (int k = 1; k <= 9; k++) {
                    int colCount = 0;
                    int colIdx = 0;
                    int colValue = 0;
                    //一行中存在多个候选值，而其他行没有
                    for (int c = col; c < col + 3; c++) {
                        boolean isFindInMay = false;
                        for (int r = row; r < row + 3; r++) {
                            if (a[r][c] > 0) continue;//当前有值时，不判断，只取候选值列表
                            if (findInMay(may, r, c, k)) {
                                isFindInMay = true;
                            }
                        }
                        if (isFindInMay) {
                            colCount++;
                            colIdx = c;
                            colValue = k;
                        }
                    }
                    if (colCount == 1) {
                        //值存在唯一行，把当前行的其他格子的候选值删除
//                        System.out.println(rowIdx);
                        if (cleanColMay(a, may, row, colIdx, colValue))
                            rs = true;
                    }
                }
            }
        }
        return rs;
    }

    /**
     * 排除行候选值
     *
     * @param a
     * @param may
     * @param row
     * @param col
     * @param rowValue
     */
    private boolean cleanRowMay(int[][] a, int[][] may, int row, int col, int rowValue) {
        String str = "第" + (row + 1) + "行，第" + (col + 1) + "列~" + (col + 3) + "列,存在唯一行值：" + rowValue + ",清除该行其他列的候选值";

        boolean isClean = false;
        for (int c = 0; c < 9; c++) {
            int idx = row * 9 + c;
            if (c >= col && c < col + 3) continue;//当前格子的忽略
            if (a[row][c] > 0) continue;//确定了值的忽略
            if (may[idx][rowValue - 1] == 1) {
                isClean = true;
                may[idx][rowValue - 1] = 0;
            }
        }
        if (isClean) {
            System.out.println(str);
        }
        return isClean;
    }

    /**
     * 排除行候选值
     *
     * @param a
     * @param may
     * @param row
     * @param col
     * @param colValue
     */
    private boolean cleanColMay(int[][] a, int[][] may, int row, int col, int colValue) {
        String str = "第" + (col + 1) + "列，第" + (row + 1) + "行~" + (row + 3) + "行,存在唯一列值：" + colValue + ",清除该列其他行的候选值";

        boolean isClean = false;
        for (int r = 0; r < 9; r++) {
            int idx = r * 9 + col;
            if (r >= row && r < row + 3) continue;//当前格子的忽略
            if (a[r][col] > 0) continue;//确定了值的忽略
            if (may[idx][colValue - 1] == 1) {
                isClean = true;
                may[idx][colValue - 1] = 0;
            }
        }
        if (isClean) {
            System.out.println(str);
        }
        return isClean;
    }

    /**
     * 区块摒除法
     * 如第1行有9，第2、3行必须有9
     * 如第1列有9，第2、3列必须有9
     * 再过滤掉候选列表
     *
     * @param a
     * @param may
     * @return
     */
    private boolean areaFilter(int[][] a, int[][] may) {
        boolean rs = false;
        for (int i = 1; i <= 9; i++) {
//            int[][] area = new int[9][9];//
            //按行扫描，遇到跟i一样的，就把这行都设置为1，就是说这一行都不能为1，并把i所在的9个格子，都设置为1
            //如果找不到，那判断，三个格式是否都已经占用数字，如果占用d了，这一行，其他的格子都不能为i，从候选列表中去掉
            for (int row = 0; row < 3; row++) {
//                if(a[row][0]>0 )
            }

        }
        return rs;
    }

    /**
     * 候选列表过滤
     *
     * @param a
     * @param may
     * @return
     */
    boolean filterMay(int[][] a, int[][] may) {
        boolean rs = false;
        for (int i = 0; i < may.length; i++) {
            int row = i / 9;
            int col = i % 9;
            //先过滤当前行，排除出现过的数字
            for (int j = 0; j < 9; j++) {
                int v = a[row][j];//当前行的每一格的值
                if (v > 0 && may[i][v - 1] == 1) {//存在列表中就设置为0
                    rs = true;
                    may[i][v - 1] = 0;//重置为0
                }
            }

            //先过滤当前列，排除出现过的数字
            for (int j = 0; j < 9; j++) {
                int v = a[j][col];//当前行的每一格的值
                if (v > 0 && may[i][v - 1] == 1) {//存在列表中就设置为0
                    rs = true;
                    may[i][v - 1] = 0;//重置为0
                }
            }

            //当前格子内排除相同的数字
            int xm = (row / 3) * 3;
            int xn = (col / 3) * 3;
            for (int m = xm; m < xm + 3; m++) {
                for (int n = xn; n < xn + 3; n++) {
                    int v = a[m][n];//当前行的每一格的值
                    if (v > 0 && may[i][v - 1] == 1) {//存在列表中就设置为0
                        rs = true;
                        may[i][v - 1] = 0;//重置为0
                    }
                }
            }
        }

        return rs;
    }

    /**
     * 基础摒除法
     * 九宫格内９只有一个唯一的位置
     * 从候选数中取数判断
     *
     * @param a
     * @param may
     */
    private boolean baseFilter(int[][] a, int[][] may) {
        boolean rs = false;
        for (int i = 0; i < may.length; i++) {
            int row = i / 9;
            int col = i % 9;
            int[] m2 = may[i];
            for (int j = 0; j < 9; j++) {
                int[][] f = new int[3][3];//占位，全为1，表示没位了，就可以确定值
                if (m2[j] > 0) {
                    int num = j + 1;//拿候选数字，跟其他的行和列比较
                    int xrow = (row / 3) * 3;//行的起始点
                    int xcol = (col / 3) * 3;//列的起始点

                    //把当前位置和存在的数字标记为1
                    f[row - xrow][col - xcol] = 1;//3*3的格子
                    for (int mrow = xrow; mrow < xrow + 3; mrow++) {
                        for (int ncol = xcol; ncol < xcol + 3; ncol++) {
                            int v = a[mrow][ncol];//当前行的每一格的值
                            if (v > 0) {//存在列表中就设置为0
                                f[mrow - xrow][ncol - xcol] = 1;//3*3的格子
                            }
                        }
                    }
                    printSmall(f);
                    //当前数字所有的9宫格，其他位置是否不能填数字
                    //当前格子内排除相同的数字
                    for (int r = xrow; r < xrow + 3; r++) {
                        if (r != row) {//本行不判断
                            for (int c = 0; c < 9; c++) {
                                if (a[r][c] == num) {
                                    //在其他行找到当前值，那这一行就屏蔽掉
                                    for (int m = 0; m < 3; m++) {
//                                        if (m == r - xrow) continue;
                                        f[r - xrow][m] = 1;//3*3的格子
                                    }
                                    break;
                                }
                            }
                        }
                    }
                    printSmall(f);
                    for (int c = xcol; c < xcol + 3; c++) {
                        if (c != col) {//本列不判断
                            for (int r = 0; r < 9; r++) {
                                if (a[r][c] == num) {
                                    //在其他列找到当前值，那这一列就屏蔽掉
                                    for (int m = 0; m < 3; m++) {
//                                        if (m == c - xcol) continue;
                                        f[m][c - xcol] = 1;//3*3的格子
                                    }
                                    break;
                                }
                            }
                        }
                    }
                    printSmall(f);
                    int oneCount = 0;//累计当前格式是否补全占位了，全占了就能确定是这个候选值
                    for (int k = 0; k < 3; k++) {
                        for (int l = 0; l < 3; l++) {
                            if (f[k][l] == 1) oneCount++;
                        }
                    }
                    if (oneCount == 9) {
                        a[row][col] = num;
                        printValue("基础摒除法", row, col, num);
                        return true;
                    }
                }
            }
        }
        return rs;
    }

    private void printSmall(int[][] f) {
        if (1 == 1) return;
        for (int k = 0; k < 3; k++) {
            for (int l = 0; l < 3; l++) {
                System.out.print(f[k][l] + " ");
            }
            System.out.println();
        }
        System.out.println("----------------");
    }

    private boolean writeMayOnlyOne(int[][] a, int[][] may) {
        boolean rs = false;
        for (int i = 0; i < may.length; i++) {
            int row = i / 9;
            int col = i % 9;
            if (a[row][col] > 0) continue;
            int[] m2 = may[i];
            int count = 0;
            int idx = 0;

            for (int j = 0; j < 9; j++) {
                if (m2[j] > 0) {
                    count++;
                    idx = j;//记录出现的索引
                }
            }
            if (count == 1) {
                printValue("只剩最后一个候选值", row, col, idx + 1);
                a[row][col] = idx + 1;//设置当前值
                m2[idx] = 0;//重置候选列表为0
                return true;
            }
        }

        //候选列表中，在行中存在唯一值（只出现过一次）
        for (int row = 0; row < 9; row++) {
            for (int i = 0; i < 9; i++) {
                int count = 0;//
                int numIdx = 0;//记录出现唯一值的那一列
                for (int col = 0; col < 9; col++) {
                    if (a[row][col] == 0) {
                        int idx = row * 9 + col;
                        if (may[idx][i] == 1) {
                            count++;
                            numIdx = col;
                        }
                    }
                }
                if (count == 1) {
                    a[row][numIdx] = i + 1;
                    printValue("行唯一候选值", row, numIdx, i + 1);
                    cleanMay(may, row, numIdx);
                    return true;
                }
            }
        }

        //候选列表中，在列中存在唯一值（只出现过一次）
        for (int col = 0; col < 9; col++) {
            for (int i = 0; i < 9; i++) {
                int count = 0;//
                int numIdx = 0;//记录出现唯一值的那一行
                for (int row = 0; row < 9; row++) {
                    if (a[row][col] == 0) {
                        int idx = row * 9 + col;
                        if (may[idx][i] == 1) {
                            count++;
                            numIdx = row;
                        }
                    }
                }
                if (count == 1) {
                    a[numIdx][col] = i + 1;
                    printValue("列唯一候选值", numIdx, col, i + 1);
                    cleanMay(may, numIdx, col);
                    return true;
                }
            }
        }

        return rs;
    }

    private void cleanMay(int[][] may, int row, int numIdx) {
        int[] m1 = may[row * 9 + numIdx];
        for (int j = 0; j < 9; j++) {
            m1[j] = 0;
        }
    }


    /**
     * 找值是否在候选列表中
     *
     * @param may
     * @param row
     * @param col
     * @param value
     * @return
     */
    private boolean findInMay(int[][] may, int row, int col, int value) {
        int[] m1 = may[row * 9 + col];
        return m1[value - 1] == 1;
    }

    private void printValue(String str, int row, int col, int value) {
        System.out.println(str + ",第" + (row + 1) + "行,第" + (col + 1) + "列,设置值为:" + value);
    }

//    private void SD2(int[][] a, int n) {
//        int i = n / 9;
//        int j = n % 9;
//        if (a[i][j] == 0) {
//            for (int k = 1; k <= 9; k++) {
//                if (test(a, i, j, k) == 1) {
//                    a[i][j] = k;//设置值
//                    if (n == 80) {
//                        print(a);
//                        return;
//                    } else {
//                        SD2(a, n + 1);
//                    }
//                    a[i][j] = 0; //回溯
//                }
//            }
//        } else {
//            if (n == 80) {
//                print(a);
//                return;
//            } else {
//                SD2(a, n + 1);
//            }
//        }
//    }

//    /**
//     * 尝试填值求解
//     *
//     * @param b
//     * @param n
//     */
//    void SD(int[][] b, int n) {
//        int i, j;
//        i = n / 9;
//        j = n % 9;              //行列
//        if (b[i][j] != 0) {        //如果该位置有数字
//            if (n == 80)
//                print(b);
//            else
//                SD(b, n + 1);
//        } else {
//            for (int k = 1; k <= 9; k++)
////            for (int k = 9; k >= 1; k--)
//                if (test(b, i, j, k) == 1) //可以
//                {
//                    b[i][j] = k;
//                    if (n == 80)
//                        print(b);
//                    else
//                        SD(b, n + 1);
//                    b[i][j] = 0; //回溯
//                }
//        }
//    }

    //判断是否可以将第i行、第j列的数设为k
    int test(int[][] a, int i, int j, int k) {
        int m, n, xm, xn;

        //检查行是否有重复数字
        for (n = 0; n < 9; n++)
            if (a[i][n] == k)
                return 0;

        //检查列是否有重复数字
        for (m = 0; m < 9; m++)
            if (a[m][j] == k)
                return 0;

        //检查当前数字所有的9个格子里是否有重复的数字
        xm = (i / 3) * 3;
        xn = (j / 3) * 3;
        for (m = xm; m < xm + 3; m++)
            for (n = xn; n < xn + 3; n++)
                if (a[m][n] == k)
                    return 0;

//        int row1, col1, row2, col2;
//        for (int x = 0; x < 81 - 1; x++) {
//            row1 = x / 9;
//            col1 = x % 9;
//            for (int y = x + 1; y < 81; y++) {
//                row2 = y / 9;
//                col2 = y % 9;
//                if (row1 != row2 && col1 != col2 && a[row1][col1] == a[row2][col2] && a[row1][col1] != 0)
//                    return 0;
//            }
//        }


        return 1;
    }

    void print(int[][] a, int[][] may) {
//        printSimple(a);
//        if(1==1)return;

        System.out.println("case: " + (count == 0 ? "原题" : count));
        count++;
        System.out.println("----------------------------------------------------------------------------------------------------------------------------");
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (a[i][j] > 0) {
                    System.out.print(a[i][j] + "\t\t\t");
                } else {
                    int[] ints = may[i * 9 + j];
                    String str = getGZ(ints);
//                    str="";
                    System.out.print(str + printTab(str));
                }
                if (j == 2) System.out.print("|\t");
                if (j == 5) System.out.print("|\t");
//                if (j == 8) System.out.println("---------------------------------------------------");
                if (j == 8) System.out.println("");
//                j==8&&i%3==2?printf("\n"):0;
            }

            if (i == 2)
                System.out.println("----------------------------------------------------------------------------------------------------------------------------");
            if (i == 5)
                System.out.println("----------------------------------------------------------------------------------------------------------------------------");
            if (i == 8)
                System.out.println("----------------------------------------------------------------------------------------------------------------------------");
        }
        System.out.println("======");
    }

    void printSimple(int[][] a) {
        System.out.println("case: " + (count == 0 ? "原题" : count));
        count++;
        for (int i = 0; i < 9; i++)
            for (int j = 0; j < 9; j++) {
//                System.out.print(a[i][j] + "\t");
                System.out.print(a[i][j] + " ");
//                if(j==2)System.out.println(" ");
//                if(j==5)System.out.println(" ");
//                if (j == 8) System.out.println("\n");
                if (j == 8) System.out.println("");
//                j==8&&i%3==2?printf("\n"):0;
            }
        System.out.println("--------------------------");
    }

    private String getGZ(int[] ints) {
        String str = "[";
        for (int k = 0; k < ints.length; k++) {
            str += ints[k] == 1 ? k + 1 : "";
        }
        str += "]";
        return str;
    }

    private String printTab(String str) {
        int tabs = 3 - str.length() / 4;
        String rs = "\t";
        for (int i = 0; i < tabs - 1; i++) {
            rs += "\t";
        }
        return rs;
    }
}
